class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val 
        self.left=left 
        self.right=right

from collections import deque
def build_level(lst):
    root=TreeNode(lst[0])
    que=deque([root])
    i=1 
    while len(que)>0 and i<len(lst):
        cur=que.popleft()
        if lst[i]: 
            cur.left=TreeNode(lst[i])
            que.append(cur.left)
        if i+1<len(lst) and lst[i+1]:
            cur.right=TreeNode(lst[i+1])
            que.append(cur.right)
        i+=2 
    return root 

def solve(root,p,q):
    if (not root) or (root==p) or (root==q): return root 
    left=solve(root.left,p,q)
    right=solve(root.right,p,q)
    if not left: return right 
    if not right: return left 
    return root 

def find(root,val):
    if not root: return None
    if root and root.val==val: return root 
    left=find(root.left,val)
    if left: return left
    return find(root.right,val)

root=build_level([3,5,1,6,2,0,8,None,None,7,4])
p=find(root,5)
q=find(root,1)
print(solve(root,p,q).val)

root=build_level([3,5,1,6,2,0,8,None,None,7,4])
p=find(root,5)
q=find(root,4)
print(solve(root,p,q).val)

root=build_level([1,2])
p=find(root,1)
q=find(root,2)
print(solve(root,p,q).val)
